package modelo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

import es.GeneradorSalida;

public class Facebook {
	
	private Grafo grafoDeUsuarios;
	private HashMap<Usuario,ArrayList<ArrayList<Usuario>>> caminosMin;
	private HashMap<Usuario,ArrayList<CaminoMinimo>> caminosMinimos;
	private HashMap<Usuario, Influyente> influyentes;
	
	public Facebook(Grafo unGrafo){
		this.grafoDeUsuarios = unGrafo;
		this.caminosMin = new HashMap<Usuario,ArrayList<ArrayList<Usuario>>>();
		this.caminosMinimos = new HashMap<Usuario,ArrayList<CaminoMinimo>>();
		this.influyentes = new HashMap<Usuario, Influyente>();
	}
	/************************************************************************************/
	public void bfs(){
		java.util.Iterator<Entry<String, Usuario>> it = this.grafoDeUsuarios.getConjunto().entrySet().iterator();
		while (it.hasNext()){
			@SuppressWarnings("rawtypes")
			Map.Entry e = (Map.Entry)it.next();
			Usuario user = (Usuario) e.getValue();
			/* si tiene amigos se aplica bfs */
			if (!user.getAmigos().isEmpty()){
				this.bfs(this.grafoDeUsuarios,user);
			}
		}
		this.generarArchivoCaminosMinimos();
		
		ArrayList<String> listaStringInfluyentes = new ArrayList<String>();
		ArrayList<Influyente> listaInfluyentes = new ArrayList<Influyente>();
		
		// Carga del hash de influyentes a una lista para hacer el sort 
		java.util.Iterator<Entry<Usuario, Influyente>> itInfluyente = this.influyentes.entrySet().iterator();
		while (itInfluyente.hasNext()){
			@SuppressWarnings("rawtypes")
			Map.Entry e = (Map.Entry)itInfluyente.next();
			Influyente influyente = (Influyente) e.getValue();
			listaInfluyentes.add(influyente);
		}
		
		Collections.sort(listaInfluyentes);
		for (Influyente influyente : listaInfluyentes){
			listaStringInfluyentes.add(influyente.getUsuario().getNombre()+": " + influyente.getInfluencia() + ".");
		}
		GeneradorSalida.GenerarArchivoSalida("datos/influyentes.txt", listaStringInfluyentes);
	}
	
	/*********************************************************/
	
	private void bfs(Grafo grafo, Usuario user) {
		ArrayList<Usuario> usersVisitados = new ArrayList<Usuario>();
		ArrayList<Usuario> marcados = new ArrayList<Usuario>();
		Cola cola = new Cola();
		ArrayList<CaminoMinimo> caminosMinimosDeUnUsuario = new ArrayList<CaminoMinimo>();
		
		cola.acolar(user);
		CaminoMinimo caminoActual = new CaminoMinimo();
		caminoActual.agregarElemento(user);
		marcados.add(user);
		
		while (!cola.isEmpty()){
			Usuario usuario = cola.desacolar();			
			for (Usuario amigo : usuario.getAmigos()){				
				if (!usersVisitados.contains(amigo) && !marcados.contains(amigo)){
					Usuario ultimo = caminoActual.getUltimo();
					if (!ultimo.getAmigos().contains(amigo)){
						caminoActual = this.caminoMinimoAsociados(caminosMinimosDeUnUsuario, amigo, usuario);
					}
					caminoActual.agregarElemento(amigo);
					if (caminoActual.size() > 2) this.analizarInfluencia(caminoActual);
					marcados.add(amigo);
					CaminoMinimo copiaDeCamino = caminoActual.copiarCamino();
					caminosMinimosDeUnUsuario.add(copiaDeCamino);
					caminoActual.eliminarUltimo();
					cola.acolar(amigo);
				}
			}
			usersVisitados.add(usuario);
		}
		this.caminosMinimos.put(user, caminosMinimosDeUnUsuario);
	}
	
	private CaminoMinimo caminoMinimoAsociados(ArrayList<CaminoMinimo> caminos, Usuario amigo, Usuario userUltimo) {
		CaminoMinimo caminoMinimo = null;		
		for (CaminoMinimo camino : caminos){
			Usuario ultimo = camino.get(camino.size()-1);
			if (ultimo.getAmigos().contains(amigo) && ultimo == userUltimo){
				caminoMinimo = camino.copiarCamino();
			}
		}
		return caminoMinimo;
	}
	
	/*************************************************************************************************************************************/
	
	public void losMasPopulares(String rutaArchivoSalida) {
		ArrayList<String> listaPopulares = new ArrayList<String>();
		listaPopulares.add("Los Más Populares:");
		listaPopulares.add("");
		
		ArrayList<Usuario> listaUsuarios = new ArrayList<Usuario>();
		
		java.util.Iterator<Entry<String, Usuario>> it = this.grafoDeUsuarios.getConjunto().entrySet().iterator();
		while (it.hasNext()){
			@SuppressWarnings("rawtypes")
			Map.Entry e = (Map.Entry)it.next();
			Usuario user = (Usuario) e.getValue();
			listaUsuarios.add(user);
		}
		Collections.sort(listaUsuarios);
		for (Usuario user : listaUsuarios){
			listaPopulares.add(user.getNombre()+": "+user.cantidadAmigos()+" amigos.");
		}
		GeneradorSalida.GenerarArchivoSalida(rutaArchivoSalida, listaPopulares);
	}
	
	/*************************************************************************************************************************************/
	
	public void losMasInfluyentes(String rutaArchivoSalida){
	/* Se aplica el algoritmo de dijkstra a todos los usuarios para poder hallar todos los caminos
	 * minimos posibles hacia todos los usurios
	 * */
	//	java.util.Iterator<Entry<String, Usuario>> it = this.grafoDeUsuarios.getConjunto().entrySet().iterator();
	//	while (it.hasNext()){
	//		@SuppressWarnings("rawtypes")
	//		Map.Entry e = (Map.Entry)it.next();
	//		Usuario user = (Usuario) e.getValue();
			/* si tiene amigos se aplica dijkstra */
	//		if (!user.getAmigos().isEmpty()){
	//			this.dijkstra(this.grafoDeUsuarios,user);
	//		}
	//	}
	//	this.generarArchivoCaminosMinimos();
		
	//	ArrayList<String> listaStringInfluyentes = new ArrayList<String>();
	//	ArrayList<Influyente> listaInfluyentes = new ArrayList<Influyente>();
	//	listaStringInfluyentes.add("Los más influyentes:");
	//	listaStringInfluyentes.add("");
	//	
		/* Carga del hash de influyentes a una lista para hacer el sort */
	//	java.util.Iterator<Entry<Usuario, Influyente>> itInfluyente = this.influyentes.entrySet().iterator();
	//	while (itInfluyente.hasNext()){
	//		@SuppressWarnings("rawtypes")
	//		Map.Entry e = (Map.Entry)itInfluyente.next();
	//		Influyente influyente = (Influyente) e.getValue();
	//		listaInfluyentes.add(influyente);
	//	}
		
	//	Collections.sort(listaInfluyentes);
	//	for (Influyente influyente : listaInfluyentes){
	//		listaStringInfluyentes.add(influyente.getUsuario().getNombre()+": " + influyente.getInfluencia() + ".");
	//	}
	//	GeneradorSalida.GenerarArchivoSalida(rutaArchivoSalida, listaStringInfluyentes);
		
		
		
		java.util.Iterator<Entry<String, Usuario>> it = this.grafoDeUsuarios.getConjunto().entrySet().iterator();
		while (it.hasNext()){
			@SuppressWarnings("rawtypes")
			Map.Entry e = (Map.Entry)it.next();
			Usuario user = (Usuario) e.getValue();
			/* si tiene amigos se aplica bfs */
			if (!user.getAmigos().isEmpty()){
				System.out.println("Para el vertice: " + user.getNombre());
				bfs(user);
			}
		}
		
		
	}
	
	/*************************************************************************************************************************************/
	
	public void recomendaciones(String rutaArchivoSalida){
		ArrayList<String> listaRecomendaciones = new ArrayList<String>();
		listaRecomendaciones.add("Recomendaciones:");
		listaRecomendaciones.add("");
		
		java.util.Iterator<Entry<String, Usuario>> itUsuario = this.grafoDeUsuarios.getConjunto().entrySet().iterator();
		while (itUsuario.hasNext()){
			
			@SuppressWarnings("rawtypes")
			Map.Entry e1 = (Map.Entry)itUsuario.next();
			Usuario user = (Usuario) e1.getValue();
			ArrayList<Usuario> amigos = user.getAmigos();
			
			/* Ver si es un nodo libre */
			if (!amigos.isEmpty()){
				int cantidadDeAmigosEnComunMaximo = 0;
				Usuario userRecomendado = null;
				
				java.util.Iterator<Entry<String, Usuario>> itOtroUsuario = this.grafoDeUsuarios.getConjunto().entrySet().iterator();
				
				while (itOtroUsuario.hasNext()){
					@SuppressWarnings("rawtypes")
					Map.Entry e2 = (Map.Entry)itOtroUsuario.next();
					Usuario user2 = (Usuario) e2.getValue();
					if ((user2 != user) && (!amigos.contains(user2))){
						int cantAmigosEnComun = 0;
						for (Usuario unAmigo : user2.getAmigos()){
							if (amigos.contains(unAmigo)){
								cantAmigosEnComun++;
							}
						}
						if (cantidadDeAmigosEnComunMaximo < cantAmigosEnComun){
							cantidadDeAmigosEnComunMaximo = cantAmigosEnComun;
							userRecomendado = user2;
						}
					}				
				}
				if (userRecomendado != null){
					listaRecomendaciones.add(user.getNombre()+": "+userRecomendado.getNombre()+" ("+cantidadDeAmigosEnComunMaximo+" amigos en común).");
				}
			}
		}
		GeneradorSalida.GenerarArchivoSalida(rutaArchivoSalida, listaRecomendaciones);
	}
	
	/* Algoritmo BFS para recorrer el grafo y encontrar los caminos minimos */
	private void bfs(Usuario nodoInicial){
		
		/* Estructura con los vertices visitados, declaracion e inicializacion */
		HashMap<String, Boolean> verticesVistiados = new HashMap<String, Boolean>();
		java.util.Iterator<Entry<String, Usuario>> iteradorUsuarios = this.grafoDeUsuarios.getConjunto().entrySet().iterator();
		while (iteradorUsuarios.hasNext()){
			
			@SuppressWarnings("rawtypes")
			Map.Entry e = (Map.Entry)iteradorUsuarios.next();
			Usuario user = (Usuario) e.getValue();
			/* Inicializamos todos en false menos el pasado por parametro */
			if (user.esElMismo(nodoInicial))
					verticesVistiados.put(user.getID(), true);
			else
					verticesVistiados.put(user.getID(), false);		
		}
		
		/* Estructura para almacenar los distintos niveles L(i) del grafo */
		ArrayList<ArrayList<Usuario>> listaNiveles = new ArrayList<ArrayList<Usuario>>();
		ArrayList<Usuario> listaNivelInicial = new ArrayList<Usuario>();
		listaNivelInicial.add(nodoInicial);
		int contadorNivel = 0; /* se denomina i en el libro */
		listaNiveles.add(contadorNivel, listaNivelInicial);
		//TODO: Set the current BFS tree T = (empty)

		/* Se itera mientras haya nodos en el nivel que se esta explorando */
		while (!listaNiveles.get(contadorNivel).isEmpty()) {
			
			ArrayList<Usuario> listaNivelProximo = new ArrayList<Usuario>();
			listaNiveles.add(contadorNivel+1, listaNivelProximo);
	
			/* Se itera sobre cada vertice del nivel */
        	System.out.print("L(" + (contadorNivel+1) + "): ");
			Iterator<Usuario> iteradorUsuarioNivelActual = listaNiveles.get(contadorNivel).iterator(); 
	        while (iteradorUsuarioNivelActual.hasNext()) {

				/* Se itera sobre todas las aristas del vertice */
	        	Usuario usuarioNivelActualTemporal = iteradorUsuarioNivelActual.next();
	        	Iterator<Usuario> iteradorAristasNivelActual = usuarioNivelActualTemporal.getAmigos().iterator();  	        			
		        while (iteradorAristasNivelActual.hasNext()) {

	        		Usuario usuarioAmigoTemporal = iteradorAristasNivelActual.next();
		        	if (!verticesVistiados.get(usuarioAmigoTemporal.getID())) {
		        	
		        		verticesVistiados.put(usuarioAmigoTemporal.getID(), true);
		        		//TODO: add edge (u,v) to the tree T
		        		listaNivelProximo.add(usuarioAmigoTemporal);
		        		System.out.print(usuarioAmigoTemporal.getNombre() + " ");
		        	}		            
		        }

	        }
	        /* Finalmente, se incrementa el contador de nivel */
	        contadorNivel++;
	        System.out.print(System.getProperty("line.separator"));
		}
	}	
	
	
	/*------------------------------------------------------------------------------------------*/
	/* Algoritmo de Dijkstra utilizando una implementacion con monticulos
	 * */
	/*
	private void dijkstra(Grafo grafo, Usuario nodoInicial){
		ColaConPrioridad cola = new ColaConPrioridad();
		int INFINITO = 1000;
		HashMap<Usuario, Integer> distancias = new HashMap<Usuario,Integer>();
		
		java.util.Iterator<Entry<String, Usuario>> it = grafo.getConjunto().entrySet().iterator();
		while (it.hasNext()){
			@SuppressWarnings("rawtypes")
			Map.Entry e = (Map.Entry)it.next();
			Usuario user = (Usuario) e.getValue();
			distancias.put(user, INFINITO);
		}
		distancias.put(nodoInicial, 0);
		cola.adicionar(nodoInicial, distancias.get(nodoInicial));
		
		ArrayList<ArrayList<Usuario>> caminosMinimosDeUnUsuario = new ArrayList<ArrayList<Usuario>>();
		ArrayList<Usuario> unCamino = new ArrayList<Usuario>();
		unCamino.add(nodoInicial);
		
		while (!cola.isEmpty()){
			Usuario user = cola.extraerMinimo();
			for (Usuario amigo : user.getAmigos()){
				if (distancias.get(amigo) >= distancias.get(user) + 1){
					unCamino = new ArrayList<Usuario>();
					unCamino.add(nodoInicial);
					boolean esAmigo = nodoInicial.getAmigos().contains(amigo);
					if (!esAmigo){
						unCamino = this.caminoMinimoAsociado(caminosMinimosDeUnUsuario, amigo, user);
					}
					unCamino.add(amigo);
					ArrayList<Usuario> caminoCopia = this.copiarCamino(unCamino);
					if (!caminosMinimosDeUnUsuario.contains(caminoCopia)){
						caminosMinimosDeUnUsuario.add(caminoCopia);
						if (unCamino.size() > 2) this.analizarInfluencia(unCamino);
					}
					int nuevaDistancia = distancias.get(user) + 1;
					distancias.put(amigo, nuevaDistancia);
					cola.adicionar(amigo, nuevaDistancia);
				}
			}
		}
		this.caminosMin.put(nodoInicial, caminosMinimosDeUnUsuario);
	}
*/
	
	/*------------------------------------------------------------------------------------------------------------------------*/
	/* Busca un camino en "caminos" de manera de el ultimo elemento sea igual a "userUltimo" y que "amigo" se encuentre
	 * entre los amigos de userUltimo para poder seguir haciendo el camino minimo
	 * */
	private ArrayList<Usuario> caminoMinimoAsociado(ArrayList<ArrayList<Usuario>> caminos, Usuario amigo, Usuario userUltimo) {
		ArrayList<Usuario> caminoMinimo = null;
		for (ArrayList<Usuario> camino : caminos){
			Usuario ultimo = camino.get(camino.size()-1);
			if (ultimo.getAmigos().contains(amigo) && ultimo == userUltimo){
				caminoMinimo = this.copiarCamino(camino);
			}
		}
		return caminoMinimo;
	}
	
	/*------------------------------------------------------------------------------------------------------------------------*/
	/* Copia un Camino minimo
	 * */
	private ArrayList<Usuario> copiarCamino(ArrayList<Usuario> camino) {
		ArrayList<Usuario> copia = new ArrayList<Usuario>();
		for (Usuario user : camino){
			copia.add(user);
		}
		return copia;
	}
	
	/*------------------------------------------------------------------------------------------------------------------------*/
	
	private void generarArchivoCaminosMinimos(){
		ArrayList<String> stringCaminos = new ArrayList<String>();
		stringCaminos.add("Caminos Mínimos:");
		stringCaminos.add("");
		
		java.util.Iterator<Entry<Usuario, ArrayList<ArrayList<Usuario>>>> it = this.caminosMin.entrySet().iterator();
		while (it.hasNext()){
			@SuppressWarnings("rawtypes")
			Map.Entry e = (Map.Entry)it.next();
			@SuppressWarnings("unchecked")
			ArrayList<ArrayList<Usuario>> listaDeCaminos = (ArrayList<ArrayList<Usuario>>) e.getValue();
			for (ArrayList<Usuario> camino : listaDeCaminos){
				stringCaminos.add(camino.toString());
			}
			stringCaminos.add("");
		}
		
		//Muestra los caminos minimos en un archivo de salida, descomentar para debug
		//GeneradorSalida.GenerarArchivoSalida("caminosminimos.txt", stringCaminos);
	}
	
	/*------------------------------------------------------------------------------------------------------------------------*/
	/* Analiza cuales son los usuarios que se encuentran en el medio de un camino minimo sin coniderar los extremos
	 * */
	
	private void analizarInfluencia(CaminoMinimo unCamino){
		for (int i = 1; i < unCamino.size()-1; i++){
			Usuario user = unCamino.get(i);
			Influyente influyente;
			if (!this.influyentes.containsKey(user)){
				influyente = new Influyente(user);
				this.influyentes.put(user, influyente);
			}else{
			    influyente = this.influyentes.get(user);
			}
			influyente.aumentarInfluencia();
		}
	}
}
